package com.lw.leetcode.tree.b;

/**
 * Created with IntelliJ IDEA.
 * tree
 * 剑指 Offer II 067. 最大的异或
 * 421. 数组中两个数的最大异或值
 *
 * @author liw
 * @version 1.0
 * @date 2022/2/14 20:48
 */
public class FindMaximumXOR {


    public static void main(String[] args) {
        FindMaximumXOR test = new FindMaximumXOR();

        // 127
        int[] items = {14, 70, 53, 83, 49, 91, 36, 80, 92, 51, 66, 70};

        // 28
//        int[] items = {3,10,5,25,2,8};

        // 0
//        int[] items = {0};

        // 6
//        int[] items = {2,4};

        // 10
//        int[] items = {8,10,2};

        int maximumXOR = test.findMaximumXOR(items);
        System.out.println(maximumXOR);
    }


    private int[] arr;
    private Node root;
    private int max;

    public int findMaximumXOR(int[] nums) {
        int length = nums.length;
        if (length == 1) {
            return 0;
        }
        if (length == 2) {
            return nums[0] ^ nums[1];
        }
        arr = new int[32];
        for (int i = 31; i >= 0; i--) {
            arr[31 - i] = (1 << i);
        }
        this.root = new Node();
        add(nums[0]);
        for (int i = 1; i < length; i++) {
            find(nums[i]);
            add(nums[i]);
        }
        return max;
    }

    private void find(int n) {
        int item = 0;
        Node node = root;
        for (int i : arr) {
            int v = n & i;
            if (v == 0) {
                if (node.right == null) {
                    node = node.left;
                    item <<= 1;
                } else {
                    node = node.right;
                    item = (item << 1) + 1;
                }
            } else {
                if (node.left == null) {
                    node = node.right;
                    item <<= 1;
                } else {
                    node = node.left;
                    item = (item << 1) + 1;
                }
            }
        }
        max = Math.max(max, item);
    }

    private void add(int n) {
        Node node = root;
        for (int i : arr) {
            int v = n & i;
            if (v == 0) {
                if (node.left == null) {
                    node.left = new Node();
                }
                node = node.left;
            } else {
                if (node.right == null) {
                    node.right = new Node();
                }
                node = node.right;
            }
        }
    }

    private class Node {
        private Node left;
        private Node right;

        public Node() {

        }
    }

}
